package org.example.myleet.p922;

/**
 * 3 ms
 */
public class Solution {
    public int[] sortArrayByParityII(int[] A) {
        int tmp;
        for (int i=0; i<A.length; i++) {
            if ((i&1) != (A[i]&1)) {
                //找到奇偶不符合的位置
                for (int j=i+1; j<A.length; j+=2) {
                    //每两个位置寻找下一个奇偶不符合的位置
                    if ((j&1) != (A[j]&1)) {
                        //找到反向奇偶不符合的位置（A[i]和A[j]是一奇一偶），交换，使互相奇偶与下标符合，完成一次整理
                        tmp = A[j];
                        A[j] = A[i];
                        A[i] = tmp;
                        break;
                    }
                }
            }
        }
        //所有位置整理完毕，完成
        return A;
    }
}
